package complexdatastructure.multidatastructure;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Classname : AllOne
 * @Description : <a href="https://leetcode.cn/problems/all-oone-data-structure/">432. 全 O(1) 的数据结构</a>
 * @Author : chentianyu
 * @Date 2023/2/13 22:38
 */


public class AllOne {
    // 定义双向链表节点
    class DLinkedList {
        List<String> keys;  // 存放字符串
        int count;  // 若字符串出现的个数为 count，则放入列表 keys
        DLinkedList pre;
        DLinkedList next;

        public DLinkedList() {
            keys = new ArrayList<>();
            this.count = 0;
        }
        public DLinkedList(int count) {
            keys = new ArrayList<>();
            this.count = count;
        }

        // 删除当前节点
        private void removeCurNode() {
            DLinkedList pre = this.pre;
            DLinkedList next = this.next;
            pre.next = next;
            next.pre = pre;
            this.next = null;
            this.pre = null;
        }
    }

    private Map<String, DLinkedList> map;  // <字符串：链表节点> 用于定位字符串所在的链表节点
    private DLinkedList head;
    private DLinkedList tail;

    public AllOne() {
        map = new HashMap<>();
        head = new DLinkedList();
        tail = new DLinkedList();
        head.next = tail;
        tail.pre = head;
    }

    private void addNode(int count, DLinkedList pre, DLinkedList next) {
        DLinkedList cur = new DLinkedList(count);
        pre.next = cur;
        next.pre = cur;
        cur.pre = pre;
        cur.next = next;
    }

    public void inc(String key) {
        DLinkedList cur = map.containsKey(key) ? map.get(key) : head;
        // 将字符串从当前节点移到下一个节点，若当前节点的下一个节点不存在则新增
        if (cur.next.count != cur.count + 1) addNode(cur.count + 1, cur, cur.next);
        cur.next.keys.add(key);
        map.put(key, cur.next);
        // 将当前节点中的字符串信息删除，若删除后当前节点中无字符则当前节点也删除
        cur.keys.remove(key);
        if (cur.keys.isEmpty() && cur != head) cur.removeCurNode();
    }

    public void dec(String key) {
        if (!map.containsKey(key)) return;
        DLinkedList cur = map.get(key);
        // 若上一个节点不是头结点，则将字符串从当前节点移到上一个节点
        if (cur.pre.count != cur.count - 1) addNode(cur.count - 1, cur.pre, cur);
        cur.pre.keys.add(key);
        map.put(key, cur.pre);
        // 将当前节点中的字符串信息删除，若删除后当前节点中无字符则当前节点也删除
        cur.keys.remove(key);
        if (cur.keys.isEmpty()) cur.removeCurNode();
    }

    public String getMaxKey() {
        if (map.isEmpty()) return "";
        return tail.pre.keys.get(0);
    }

    public String getMinKey() {
        if (map.isEmpty()) return "";
        return head.next.keys.get(0);
    }
}
